package com.datastructure.test.findgreatestsumofsublistnode;

public class FindGreatestSumOfSubListNode {

    public static void main(String[] args) {
        FindGreatestSumOfSubListNode findGreatestSumOfSubListNode = new FindGreatestSumOfSubListNode();

    }

    public int FindGreatestSumOfSubArray (ListNode head) {
        // write code here
        if(head==null){
            return -1;
        }
        int length = getLengthFromListNode(head);
        if(length==1){
            return head.val;
        }
        int[] data = new int[length];
        int index = 0;
        while (head!=null){
            data[index]= head.val;
            head=head.next;
            index++;
        }
        int sum = 0;
        int max = data[0];
        for (int i = 0; i < length; i++) {
            sum=Math.max(sum+data[i],data[i]);
            max=Math.max(max,sum);
        }
        return max;
    }

    private int getLengthFromListNode(ListNode head) {
        int length = 0;
        while (head!=null){
            length++;
            head=head.next;
        }
        return length;
    }

    public int FindGreatestSumOfSubArray1 (ListNode head) {
        // write code here
        int ret = head.val, pre = 0;
        while (head != null) {
            pre = Math.max(pre + head.val, head.val);
            ret = Math.max(ret, pre);
            head = head.next;
        }
        return ret;
    }
}

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
}
